package realDeal;

public class Bucket {
	private static final int BUCKET_FULL = -1; // TODO: magic number?
	private static final int LAST_STEP = -2; // TODO: magic number?

	/**
	 * a potentially full-size bucket which will be allocated in case of bucket
	 * overflow (aka fl flag)
	 */
	private FullSizeBucket fullBucket;

	/**
	 * an array of all steps in bucket (aka A1,A2...Ap arrays)
	 */
	private Step[] steps;

	/**
	 * an array of flags which indicate the migration of a counter to its
	 * appropriate full-size bucket, the migration is done lazily
	 */
	private boolean[] migratedCounters;

	/**
	 * Create a new bucket with a given number of steps where each step is of a
	 * given length and width, and a given maximum length of a each counter
	 * 
	 * @param stepLengths
	 *            -
	 * @param stepWidths
	 *            -
	 * @param numOfSteps
	 *            -
	 */
	public Bucket(int[] stepLengths, int[] stepWidths, int numOfSteps) {
		fullBucket = null;
		steps = new Step[numOfSteps];
		initializeSteps(stepLengths, stepWidths, numOfSteps);
		migratedCounters = new boolean[stepLengths[0]];
	}

	/**
	 * 
	 * @param stepLengths
	 * @param stepWidths
	 * @param numOfSteps
	 */
	private void initializeSteps(int[] stepLengths, int[] stepWidths,
			int numOfSteps) {
		for (int i = 0; i < stepLengths.length; i++) {
			steps[i] = new Step(i, stepLengths[i], stepWidths[i], numOfSteps);
		}
	}

	private int rank(int stepNum, int start, int finish) {
		int counter = 0;
		for (int i = start; i < finish; i++) {
			counter += steps[stepNum].isOverflowedMapSet(i) ? 1 : 0;
		}
		return counter;
	}

	/**
	 * 
	 * receives a step number and a counter's location in it.
	 * returns this counter location in the next step.
	 * if the next step is full, and the counter cannot overflow there,
	 * then the response is "BUCKET_FULL". and the full bucket is being
	 * Initialized if necessary.
	 * @param stepNum
	 *            - the current step (aka i in Ai)
	 * @param counterNum
	 *            - the location in the current step (aka j in Cj)
	 * @return BUCKET_FULL- can't over flow to next step- go to full size bucket
	 *         LAST_STEP- can't perform slide on the last step
	 */
	private int slide(int stepNum, int counterNum) {
		if (stepNum >= steps.length - 1) {
			return LAST_STEP;
		}
		if (steps[stepNum].isOverflowedMapSet(counterNum)) {
			// the counter as already overflowed and received a place in the
			// next step
			return rank(stepNum, 0, counterNum);
		}
		if (rank(stepNum, 0, steps[stepNum].getAmountOfCounters()) >= steps[stepNum + 1]
				.getAmountOfCounters()) {
			// the maximum amount of counters over flowed to the next step.
			// this counter can't overflow to the next step- the bucket is full.
			this.fullBucket = new FullSizeBucket(steps[0].getAmountOfCounters());
			// initialize the full size bucket
			return BUCKET_FULL;
		}
		// can over flow to the next step
		steps[stepNum].setOverflowedMap(counterNum, true);
		// mark's that the current location in the step as over flowed
		int locationInNextStep = rank(stepNum, 0, counterNum);
		//the current counter location in the next step
		if (rank(stepNum, (counterNum + 1),
				steps[stepNum].getAmountOfCounters()) > 0) {
			//if counters in bigger indexes in this step has overflowed, their location in the next step has shifted.
			//thus, need to shift the values in the next step
			steps[stepNum + 1].shift(locationInNextStep);
		}
		return locationInNextStep;
	}

	private int cumulativeWidths(int stepNum) {
		int sum = 0;
		for (int i = 0; i <= stepNum; i++) {
			sum += steps[i].getCounterAt(0).length; // 0 could be any index
		}
		return sum;
	}

	/**
	 * Move a counter on with a given index to the full-size bucket Assume the
	 * increment has not been performed yet
	 * 
	 * @param counterIndex
	 *            - the index of the counter to move
	 */
	private void migrateCounter(int counterIndex) {
		int realIndex=counterIndex;
		boolean overflow = true;
		int stepIndex = 0, offset = 0;
		Step step;
		while (overflow) { // overflow in this step
			step = steps[stepIndex];
			boolean[] counter = step.getCounterAt(counterIndex);
			for (int i = 0; i < counter.length; i++) {

				if (counter[i]) { // bit is on
					fullBucket.setBitAt(realIndex, counter.length - i + offset, true);
				}
			}
			if (!step.isOverflowedMapSet(counterIndex)) { // no overflow
				overflow = false;
			}
			
			counterIndex = rank(stepIndex, 0, counterIndex); // next
																// position
			stepIndex++;
			offset += counter.length;
		}

	}

	/**
	 * increments the counter
	 * 
	 * @param itemIndex
	 *            - the index of the counter in the first subArray
	 */
	public void incrementCounter(int itemIndex) {
		int counterIndex = itemIndex;
		// here we check if we generated the fullSuzeBacket yet
		if (migratedCounters[itemIndex]) {
			fullBucket.incrementFull(counterIndex);
			return;
		}
		if (fullBucket != null && migratedCounters[itemIndex] == false) {
			// the bucket is full but the counter didn't migrate
			migrateCounter(itemIndex);
			fullBucket.incrementFull(itemIndex);
			this.migratedCounters[itemIndex] = true;
			return;
		}
		// the bucket isn't full
		for (int i = 0; i < steps.length; i++) {
			// checks if the increment of the sub counter has a carry
			if (steps[i].incrementSubcounter(counterIndex) == false) {
				break;
			} else {
				counterIndex = slide(i, counterIndex);
				// checks if we cant move to the next sub array
				if (counterIndex == BUCKET_FULL) {
					migrateCounter(itemIndex);
					this.fullBucket.setBitAt(itemIndex,
							cumulativeWidths(i) + 1, true);
					this.migratedCounters[itemIndex] = true;
					return;
				}
			}
		}
	}

	/**
	 * Return the actual value of a counter based on its index in the bucket
	 * 
	 * @param counterIndex
	 *            - the index of the desired counter
	 * @return - the value of the counter in the bucket
	 */
	public int getValueOfCounter(int counterIndex) { // actual index
		if (migratedCounters[counterIndex]) { // bucket overflow
			return fullBucket.getFull(counterIndex);
		}

		boolean overflow = true;
		int sum = 0, mult = 1;
		int stepIndex = 0;
		Step step;
		while (overflow) { // overflow in this step
			step = steps[stepIndex];
			boolean[] counter = step.getCounterAt(counterIndex);
			for (int i = counter.length - 1; i >= 0; i--) {
				if (counter[i]) { // bit is on
					sum += mult;
				}
				mult = mult << 1;
			}
			if (!step.isOverflowedMapSet(counterIndex)) { // no overflow
				overflow = false;
			}
			counterIndex = rank(stepIndex, 0, counterIndex); // next
																// position
			stepIndex++;
		}
		return sum;
	}

	/**
	 * Returns whether the bucket is empty or not
	 */
	public boolean isEmpty() {
		// iterate over steps
		for (int i = 0; i < steps.length; i++) {
			// iterate over counters
			for (int j = 0; j < steps[i].getAmountOfCounters(); j++) {
				boolean[] counter = steps[i].getCounterAt(j);
				// iterate over bits
				for (int k = 0; k < counter.length; k++) {
					if (counter[k]) { // found non zero value
						return false;
					}
				}
			}
		}
		return true;
	}

	/**
	 * Returns whether the bucket has overflowed or not
	 * 
	 * @return - true if the bucket has overflowed or false otherwise
	 */
	public boolean isOverflowed() {
		return this.fullBucket != null;
	}
}
